iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 9
1
自我挑戰組

神羅天征! 一起(爆肝)征服程式解題系列 第 9

[Day 9] LeetCode - 409 Longest Palindrome

  • 分享至 

  • xImage
  •  

本篇同步發布於Blog: [解題] LeetCode - 409 Longest Palindrome

平台:

LeetCode

題號:

409 - Longest Palindrome

題目連結:

https://leetcode.com/problems/longest-palindrome/

題目說明:

        輸入1個字串,裡面有不同的字元,且大小寫也視為不同,求從這些字元組成最大回文的長度。

比如範例輸入的abccccdd,能組成最大長度為7的回文,有可能是ccdadcc或者其他的組合。

解題方法:

分析每個字元出現的頻率,假如X字元出現偶數次,則它一定能全部拿去組回文。但如果X字元出現奇數次,則只能取它的數量-1後再拿去組回文,假如目前回文的長度是偶數,則剛剛那筆奇數次的字元,被-1的數量要再補上去,這樣仍是回文。

以範例輸入的abccccdd:

  • a的出現次數為1,能組成回文,目前回文長度為1
  • b的出現次數為1,無法加進回文,回文長度仍不變
  • c的出現次數為4,能組成回文,目前回文長度為5
  • d的出現次數為2,能組成回文,目前回文長度為7

所以最長的長度為7。

難度為Easy

程式碼 (C++ 與 C#):

#include <iostream>
#include <string>
using namespace std;
 
class Solution {
public:
    int longestPalindrome(string s) {
        int letters[128] = {0};
 
        for(char c : s){
            letters[c]++;
        }
 
        int ans = 0;
        for(int i = 0 ; i < 128;++i){
            int curLen = letters[i];
            if(letters[i] % 2 == 1){
                curLen--;
            }
 
            ans += curLen;
            if(ans % 2 == 0 && letters[i] % 2 == 1){
                ans++;
            }
        }
 
        return ans;
    }
 
};
 
int main() {
	Solution sol;
	cout << sol.longestPalindrome("abccccdd") << endl;
	return 0;
}
using System;

namespace LeetCode409
{
	public class Solution {
		public int LongestPalindrome(string s) {
			int[] letters = new int[128];
			foreach(char c in s){
				letters[(int)c]++;
			}

			int ans = 0;
			for(int i = 0 ; i < 128;++i){
				int curLen = letters[i];
				if(letters[i] % 2 == 1){
					curLen--;
				}

				ans+=curLen;
				if(ans % 2 == 0 && letters[i] % 2 == 1){
					ans++;
				}
			}
			return ans;
		}
	}
	
	public class Program
	{
		public static void Main()
		{
			Solution sol = new Solution();
			Console.WriteLine(sol.LongestPalindrome("abccccdd"));
			Console.Read();
		}
	}
}

GITHUB位置(C++ 與 C#):

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%2B%2B/400-499/409.cpp

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%23/400-499/409.cs


上一篇
[Day 8] POJ - 1182 食物链
下一篇
[Day 10] LeetCode - 200 Number of Islands
系列文
神羅天征! 一起(爆肝)征服程式解題30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言